class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if len(haystack) < len(needle):
            return -1

        if len(needle) == 0:
            return 0
        # elif len(needle) == 1:
        #     try:
        #         return haystack.index(needle)
        #     except ValueError:
        #         return -1
        else:
            return self.check(haystack, needle)
        return haystack.find(needle)

    def check(self, haystack: str, needle: str):
        i, j= 0, 0
        n, m = len(haystack), len(needle)
        lps = self.getLps(needle)
        while i < n:
            if needle[j] == haystack[i]:
                i += 1
                j += 1
            if j == m:
                return i- m
            if j < m and i < n and needle[j] != haystack[i]:
                if j != 0:
                    j = lps[j - 1]
                else:
                    i += 1
        return -1


    def getLps(self, needle: str):
        lps = [0] * len(needle)
        j, i = 0, 1
        while i < len(needle):

            print('=============================')
            print(''.join([str(i) for i in lps]))
            po = [' '] * len(needle)
            po[i] = 'i'
            po[j] = 'j'
            print(''.join(po))
            print(needle)

            if needle[j] == needle[i]:
                lps[i] = j + 1
                i += 1
                j += 1
            else:
                if j == 0:
                    lps[i] = 0
                    i += 1
                else:
                    j = lps[j - 1]

        return lps


solu = Solution()
# print(solu.strStr("hello", "ll"))
# print(solu.strStr("aaaaa", "bba"))
# print(solu.strStr("aaa", "aa")) # 不对
# print(solu.strStr("", "a"))
# print(solu.strStr("mississippi", "a"))

print(solu.getLps('aabaabaaa'))